package org.example.ch13;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/word-search-ii/
 * 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
 *
 * 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母在一个单词中不允许被重复使用。
 *
 */
public class FindWords {

    Set<String> set = new HashSet<>();
    List<String> ans = new ArrayList<>();
    String[][] board;
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int n,m;
    boolean[][] vis = new boolean[15][15];

    public List<String> findWords(String[][] _board,String[] words){
        this.board = _board;
        m = board.length;
        n = board[0].length;

        for (String s:words){
            set.add(s);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                vis[i][j] = true;
                sb.append(board[i][j]);
                dfs(i,j,sb);
                vis[i][j] = false;
                sb.deleteCharAt(sb.length()-1);
            }
        }
        return ans;
    }

    public void dfs(int i,int j,StringBuilder sb){
        //递归的终结条件
        if(sb.length()>10){
            System.out.println("最后的字符串:"+sb.toString());
            return;
        }
        //如果匹配到了
        if(set.contains(sb.toString())){
            set.remove(sb.toString());
            ans.add(sb.toString());
        }

        //执行本层逻辑
        for (int[] d : dirs)  {
            int dx = i+d[0];
            int dy = j+d[1];

            if(dx<0 || dx>=m||dy<0||dy>=n){
                continue;
            }
            if(vis[dx][dy]){
                continue;
            }
            vis[dx][dy]=true;
            sb.append(board[dx][dy]);
            System.out.println("==每次拼接的字符："+sb.toString());

            //下探到下一层递归，传入主角
            dfs(dx,dy,sb);
            //重置本层状态
            vis[dx][dy]=false;
            sb.deleteCharAt(sb.length()-1);
        }
    }

    public static void main(String[] args) {
        FindWords find = new FindWords();
        String[][] board = new String[][]{
                {"o","a","a","n"},
                {"e","t","a","e"},
                {"i","h","k","r"},
                {"i","f","l","v"}};
        String[] words = new String[]{"oath","pea","eat","rain"};


       List<String> list = find.findWords(board,words);
       for (String str:list){
           System.out.println("匹配的字符串："+str);
       }
    }
}
